﻿using System.Diagnostics;
using System.Text;
/// <summary>
/// https://leetcode-cn.com/problems/text-justification/
/// </summary>
public class Solution
{
    private class LineBuilder
    {
        public LineBuilder(int maxWidth, bool leftAlign = false)
        {
            this.MaxWidth = maxWidth;
            this.LeftAlign = leftAlign;
            this.totalLength = 0;
            this.words = new List<string>();
        }

        public bool LeftAlign { get; set; }
        public int MaxWidth { get; }

        private int totalLength;
        private readonly List<string> words;
        public IReadOnlyList<string> Words => this.words.AsReadOnly();

        public bool TryAppend(string word)
        {
            var newTotal = this.totalLength + word.Length;
            var minWhiteSpace = this.words.Count;
            if (newTotal + minWhiteSpace <= this.MaxWidth)
            {
                this.words.Add(word);
                this.totalLength = newTotal;
                return true;
            }
            return false;
        }

        public override string ToString()
        {
            if (this.LeftAlign)
                return string.Join(' ', this.words).PadRight(this.MaxWidth, ' ');

            if (this.words.Count == 1)
                return this.words[0].PadRight(this.MaxWidth, ' ');

            Stack<int> whiteSpacesCounts = new Stack<int>();
            whiteSpacesCounts.Push(0);
            var lastWhiteSpacesCount = this.MaxWidth - this.totalLength;
            for (int lastPlacesCount = this.words.Count - 1; lastPlacesCount > 0; lastPlacesCount--)
            {
                var count = lastWhiteSpacesCount / lastPlacesCount;
                lastWhiteSpacesCount -= count;
                whiteSpacesCounts.Push(count);
            }

            StringBuilder stringBuilder = new StringBuilder(this.MaxWidth);
            foreach (var word in this.words)
                _ = stringBuilder.Append(word).Append(' ', whiteSpacesCounts.Pop());
            return stringBuilder.ToString();
        }
    }

    public IList<string> FullJustify(string[] words, int maxWidth)
    {
        List<LineBuilder> lines = new List<LineBuilder>();
        LineBuilder current = new LineBuilder(maxWidth);
        foreach (var word in words)
        {
            if (!current.TryAppend(word))
            {
                lines.Add(current);
                current = new LineBuilder(maxWidth);
                var shouldBeTrue = current.TryAppend(word);
                Debug.Assert(shouldBeTrue);
            }
        }
        current.LeftAlign = true;
        lines.Add(current);
        return lines.Select((line) => line.ToString()).ToArray();
    }
}